import BinarySearchTree from './binary-search-tree';
import { ICompareFunction, defaultCompare, Compare } from '../util';
import Node from './models/node';

enum BalanceFactor {
    UNBALANCED_RIGHT = -2, // 平衡因子为-2，代表节点的右侧比左侧过长。
    SLIGHTLY_UNBALANCED_RIGHT = -1, // 平衡因子为-1，右侧比左侧多一个
    BALANCED = 0, // 平衡因子为0，平衡
    SLIGHTLY_UNBALANCED_LEFT = 1, // 平衡因子为1，左侧比右侧多一个
    UNBALANCED_LEFT = 2, // 平衡因子为2，代表节点的左侧比右侧过长
}

/**
 * 自平衡二叉搜索树(AVL)是特殊的二叉搜索树，特殊之处在于树中任何一个节点的左子树和右子树高度最多相差1，
 * AVL树在添加或移除节点时会尽可能尝试转换为完全二叉树。
 */
export default class AVLTree<T> extends BinarySearchTree<T> {
    constructor(compareFn: ICompareFunction<T> = defaultCompare) {
        super(compareFn);
    }
    /**
     * 计算节点所在子树的高度
     * 例：
     * 一个节点没有后代，它所在子树的高度为0
     * 一个节点只有子节点这一代，它所在子树的高度为1
     */
    private getNodeHeight(node: Node<T>): number {
        if (node == null) {
            return -1;
        }
        return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
    }
    /**
     * 计算某个节点的平衡因子
     */
    private getBalanceFactor(node: Node<T>) {
        // 左侧子树高度减去右侧子树高度
        const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
        switch (heightDifference) {
            case -1:
                return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT; // 平衡因子为1，右侧略微不平衡多1层
            case 1:
                return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT; // 平衡因子为1，左侧略微不平衡多1层
            case -2:
                return BalanceFactor.UNBALANCED_RIGHT; // 平衡因子为-2，代表节点的右侧比左侧多2层
            case 2:
                return BalanceFactor.UNBALANCED_LEFT; // 平衡因子为2，代表节点的左侧比右侧多2层
            default:
                return BalanceFactor.BALANCED; // 左右完全平衡
        }
    }
    /**
     * 左-左形式：需要右旋转
     * 将2插到5的左侧子节点，20那个节点将会不平衡，需要将20那
     * 个节点进行右旋转。15那个节点会挡住20那个节点，那么就需
     * 要先将15那个节点放到20那个节点的左侧子节点上，最后将20
     * 这个节点放到10这个节点的右侧子节点上，这样就完成了右旋
     * 转。
     * --------------------------------------------------
     *        20               10
     *       /  \             /  \
     *      10   25          5    20
     *     / \       ——>    /     / \
     *    5   15           2     15  25
     *   ^
     *  2
     * --------------------------------------------------
     */
    private rotationLL(node: Node<T>): Node<T> {
        // 临时保存不平衡节点的左侧子树
        const temp = node.left;
        // node准备右旋转，而temp的right上有多余的节点
        // 这个多余的节点可以移到node的left上
        node.left = temp.right;
        // 完成旋转也就是node会旋转到temp的right上
        temp.right = node;
        return temp;
    }
    /**
     * 右-右形式：需要左旋转
     * 将28插到25的右侧子节点，10那个节点将会不平衡，需要将10
     * 那个节点进行左旋转。15那个节点会挡住10那个节点，那么就
     * 需要先将15那个节点放到10那个节点的右侧子节点上，最后将
     * 10这个节点放到20这个节点的左侧子节点上，这样就完成了左
     * 旋转。
     * --------------------------------------------------
     *    10                    20
     *   /  \                  /  \
     *  5   20                10   25
     *      / \       ——>    /  \    \
     *     15  25           5   15    28
     *          ^
     *           28
     * --------------------------------------------------
     */
    private rotationRR(node: Node<T>): Node<T> {
        // 临时保存右侧子树（node.right）
        const temp = node.right;
        // node准备左旋转，而temp的left上有多余的节点
        // 这个多余的节点可以移到node的right上
        node.right = temp.left;
        // 完成旋转也就是node会旋转到temp的left上
        temp.left = node;
        return temp;
    }
    /**
     * 左-右形式：先需要左旋转最后需要右旋转
     * 将18插到15的右侧子节点，20那个节点将会不平衡，需要将10
     * 那个节点进行左旋转，最后对20那个节点进行右旋转。
     * --------------------------------------------------
     *      20               20              15
     *     /  \             /  \            /  \
     *    10   25          15   25         10   20
     *   / \       ——>    /  \      ——>   /    /  \
     *  5   15           10  18          5    18   25
     *       ^          /
     *        18       5
     * --------------------------------------------------
     */
    private rotationLR(node: Node<T>): Node<T> {
        // 对不平衡节点的左侧子节点进行左旋转
        node.left = this.rotationRR(node.left);
        // 对不平衡节点进行右旋转
        return this.rotationLL(node);
    }
    /**
     * 右-左形式：先需要右旋转最后需要左旋转
     * 将13插到15的左侧子节点，10那个节点将会不平衡，需要将20
     * 那个节点进行右旋转，最后对10那个节点进行左旋转。
     * --------------------------------------------------
     *   10               10                  15
     *  /  \             /  \                /  \
     * 5   20           5   15              10   20
     *     / \     ——>      / \     ——>    /  \    \
     *    15  25           13  20         5   13   25
     *    ^                     \
     *   13                      25
     * --------------------------------------------------
     */
    private rotationRL(node: Node<T>): Node<T> {
        // 对不平衡节点的右侧子节点进行右旋转
        node.right = this.rotationLL(node.right);
        // 对不平衡节点进行左旋转
        return this.rotationRR(node);
    }
    /**
     * 向树中插入一个新的键
     */
    public insert(key: T) {
        this._root = this.insertNode(this._root, key);
    }
    /**
     * 插入一个节点的左侧还是右侧，用比较函数来比较
     * 插入后还需要反过来对node进行平衡检查
     */
    protected insertNode(node: Node<T>, key: T) {
        if (node == null) {
            return new Node<T>(key); // 直接return，新键也不需要对这个键作平衡操作
        }
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // key小于node.key
            node.left = this.insertNode(node.left, key); // 插左边
        } else if (this._compareFn(key, node.key) === Compare.BIGGER_THAN) { // key大于node.key
            node.right = this.insertNode(node.right, key); // 插右边
        } else { // 键重复，无需插入
            return node; // 直接return，键重复也不需要对这个键作平衡操作
        }
        const balanceFactor = this.getBalanceFactor(node); // node的平衡因子
        if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) { // node不平衡并且属于左边高
            if (this._compareFn(key, node.left.key) === Compare.LESS_THAN) { // 新键在node的左子树的左子树上
                node = this.rotationLL(node);
            } else { // 新键在node的左子树的右子树上
                node = this.rotationLR(node);
            }
        } else if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) { // node不平衡并且属于右边高
            if (this._compareFn(key, node.right.key) === Compare.BIGGER_THAN) { // 新键在node的右子树的右子树上
                node = this.rotationRR(node);
            } else {
                node = this.rotationRL(node);
            }
        }
        return node; // 迭代结合return，反过来对每次的node进行平衡检查
    }
    /**
     * 删除元素，重写父类的同名方法，会用到父类的逻辑再新增平衡操作的逻辑
     * 特殊之处：子类super调用父类同名方法，并且父类的那个方法递归调用自身。
     * 调用顺序就是子类removeNode方法——>父类removeNode方法——>递归调用子类
     * removeNode方法——>父类removeNode方法——>递归调用子类的removeNode方法，
     * 循环调用至边界条件。
     */
    protected removeNode(node: Node<T>, key: T) {
        node = super.removeNode(node, key);
        if (node == null) {
            return node; // 空的null不需要平衡
        }
        // 从每次删除的节点开始，自底向上检查平衡性
        const balanceFactor = this.getBalanceFactor(node);
        if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) { // 左子树不平衡
            // 左子树的左节点的平衡因子，如果这个平衡因子是0或者1，代表左子树是左-左型
            const balanceFactorLeft = this.getBalanceFactor(node.left);
            if (balanceFactorLeft === BalanceFactor.BALANCED ||
                balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
                node = this.rotationLL(node);
            } else if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
                node = this.rotationLR(node);
            }
        } else if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) { // 右子树不平衡
            // 右子树的右节点的平衡因子，如果这个平衡因子是0或者1，代表右子树是右-右型
            const balanceFactorRight = this.getBalanceFactor(node.right);
            if (balanceFactorRight === BalanceFactor.BALANCED ||
                balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
                node = this.rotationRR(node);
            } else if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
                node = this.rotationRL(node);
            }
        }
        return node;
    }
}
